#include<iostream>
#include<vector>
using namespace std;
/**
 * 思路1：排序，然后找中间元素O(n) O(n) 空间上要申请新数组
 * 思路2：双指针遍历，将比较小的那个指针往后移 
 *      同时计数，当计数为数组长度时，指针就是中位数
 * O(n) 和 O（1)不用申请空间
 * 思路3：根据数学性质两个数组等长，两个数组的中位数将两个数组分成了大小两部分
 * 但是剩下的两部分并没有办法保证长度我
 * 
 */
auto get_mid(vector<int> arr1,vector<int> arr2){
    int count=0;
    int p1=0,p2=0;
    while (count<arr1.size())
    {   
        if(arr1[p1]>arr1[p2])p1++;
        else p2++;
    }
    //p1 p2比较大的哪一个作为最后的返回值
    //因为找的是第n大的数字
    if(p1>p2){
        return arr1[p1];
    }else{
        return arr2[p2];
    }
}


int main(){
    //两个等长的，排好序的数组
    vector<int> arr1={11,13,15,17,19};
    vector<int> arr2={2,4,6,8,20}
    //6和15，取他们中间的为{8,20} 和 {11,13}
    //这个东西我证不出来，用O(n)的那个好了
}